Lexikográfiai szélességi keresés

A számítástechnikában a lexikográfiai szélességi keresés (Lex-BFS) egy lineáris idejű algoritmus egy gráf csúcsainak rendezésére. Az algoritmus különbözik a szélességi kereséstől, és olyan sorrendet követ, amely összhangban van a szélességi kereséssel.

A lexikográfiai szélességi keresési algoritmus a partíció finomításának ötletén alapszik, és először Donald J. Rose, Robert E. Tarjan és George S Lueker (1976) dolgozta ki. A téma részletesebb áttekintését Corneil (2004) végezte. Szubrutinként használták más gráfalgoritmusokban is, ideértve a húr menti gráfok felismerését és a távolság-öröklött gráfok optimális színezését.

Háttér

Az első szélességi keresési algoritmust általában a következő folyamat határozza meg:

• Inicializálja a gráfcsúcsok sorát úgy, hogy a grafikon kezdő csúcsa a sor egyetlen eleme.
• Amíg a sor nem üres, távolítsa el egy v csúcsot a sorból, és adja hozzá a sorhoz az összes többi olyan csúcsot, amely a v élével elérhető, v amelyeket még nem adtak hozzá a korábbi lépésekben.

Ugyanakkor ahelyett, hogy meghatározná a csúcsot, hogy minden egyes lépésben szükségszerűen válasszon, mint amelyet a sor késleltetett művelete eredményez, a csúcsok azonos sorozatát deklaratív módon lehet meghatározni ezen csúcsok tulajdonságai alapján.Összefoglalva a szabványos szélességű első keresés csak a következő szabálynak a többszöri alkalmazásának eredménye:

• Ismételten adjon ki egy v csúcsot, mindegyik lépésnél válasszon olyan v csúcsot, amelyet még nem választottak meg, és amelyben egy előd van (egy csúcs, amelynek v éle van), a lehető legkorábbi szakaszban.

Bizonyos esetekben a csúcsoknak az elődeik kimeneti helyzete alapján történő rendezése kapcsolatban állhat - két különböző csúcsnak ugyanaz a legkorábbi elődjével. Ebben az esetben a két csúcs kiválasztásának sorrendje tetszőleges lehet. A lexikográfiai szélességi keresés eredménye abban különbözik a normál szélesség első kereséstől, hogy következetes szabály van az ilyen kapcsolatok megszakítására. A lexikográfiai szélességi keresésnél a kimeneti sorrend a sorrend által előállított sorrend:

• Ismételten egy v csúcsot adjunk meg, mindegyik lépésben kiválasztva egy olyan v csúcsot, amelyet még nem választottak meg, és amelynek a már kimeneti elődeinek teljes halmaza lexikografikus sorrendben a lehető legkisebb.

Tehát, ha két v és w csúcsnak ugyanaz a legkorábbi elődje, mint bármely más nem választott csúcsnál, akkor a szokásos szélesség első keresési algoritmus önkényesen rendezi őket. Ehelyett ebben az esetben a LexBFS algoritmus v és w között választhat a második legkorábbi elődeik kimeneti sorrendje alapján változik. Ha csak egyikük rendelkezik egy második legkorábbi elődjével, amelyet már kiadtak, akkor azt választják. Ha mind a v mind a w ugyanaz a legkorábbi elődje, akkor a döntetlen megszakad, ha figyelembe vesszük a harmadik legkorábbi elődeiket, és így tovább.

Ha ezt a szabályt közvetlenül alkalmazza a csúcsok e szabály szerinti összehasonlításával, az algoritmus nem hatékony. Ehelyett a lexikográfiai szélességi keresés egy meghatározott particionálási adatszerkezetet használ annak érdekében, hogy ugyanazt a sorrendet eredményesebben hozzák létre, ugyanúgy, mint a szokásos szélesség-első keresés sor adatszerkezetet használ a rendezés hatékonyságához.

Algoritmus

A lexikográfiai szélességi keresési algoritmus a standard szélességi keresés csúcsainak sorát cseréli a csúcsok sorrendjére. A sorozat halmazai a fennmaradó csúcsok partícióját képezik. Mindegyik lépésben a sorozat első halmazának v csúcsát eltávolítják a sorozatból, és ha ez az eltávolítás azt okozza, hogy a halmaz üres, akkor a halmazt eltávolítják a sorozatból. Ezután mindegyik készletnél a sorozatban helyébe két altípus: a szomszédok a v, és a nem-szomszédai v -nek. A szomszédok részhalmaza korábban helyezkedik el a sorrendben, mint a nem szomszédok részhalmaza. A pszeudokódban az algoritmus a következőképpen fejezhető ki:

• Inicializálja a halmazok sorozatát, hogy egyetlen csúcsot tartalmazzon, amely minden csúcsot tartalmaz.
• Inicializálja a csúcsok kimeneti sorozatát, hogy üres legyen.
• Amíg Σ nem üres:
  • Keresse meg és távolítsa el v csúcs az első készlet Σ
  • Ha az elindulásnál az első készlet üres, vegye ki a Σ-ből
  • Adja hozzá a v értéket a kimeneti sorozat végéhez.
  • Mindegyik v-w élnél, hogy w továbbra is az S halmazhoz tartozik Σ-ben:
    • Ha a w feldolgozó S sorozatot még nem cserélték le v feldolgozása közben, hozzon létre egy új üres T helyettesítő készletet, és helyezze az S elé a sorozatban; ellenkező esetben hagyjuk, hogy T legyen az S előtti halmaz.
    • Mozgassa w- t S-ből T-be, és ha ez S üres lesz, vegye S- t Σ-ből.

Mindegyik csúcsot egyszer dolgozzuk fel, mindegyik élt csak akkor vizsgáljuk meg, amikor a két végpontja feldolgozásra kerül, és (a megfelelő ábrázolással az Σ -ben szereplő halmazokhoz, amely lehetővé teszi az elemek mozgatását állandó készletben az egyik halmazból a másikba) a belső hurok minden iterációjával csak állandó időt vesz igénybe. Ezért, az egyszerűbb gráfkeresési algoritmusokhoz, például a szélesség első keresés és a mélység első kereséshez hasonlóan, ez az algoritmus lineáris időt vesz igénybe.

Az algoritmust lexikográfiai szélességi keresésnek nevezzük, mivel az általa előállított sorrend olyan rendezés, amelyet szintén első szélességű kereséssel állíthatunk elő, és mert ha a rendezést egy gráf szomszédsági mátrixának sorainak és oszlopainak indexelésére használjuk, az algoritmus a sorokat és oszlopokat lexikográfiai sorrendbe rendezi.

Alkalmazások

Húrgráfok

A G gráfot akkor határozzuk meg húrnak, ha csúcsainak tökéletes kiküszöbölési sorrendje van, olyan sorrendben, hogy bármely v csúcs esetében a szomszédok, amelyek késõbb fordulnak elő a rendezésben. A a lexikográfiai rendezés fordítottja mindig tökéletes eliminációs rendezésnek. Ezért a következő algoritmussal kipróbálható, hogy egy gráf lineáris időben húr-e:

• Használjon lexikográfiai szélességi keresést a G lexikográfiai sorrendjének meghatározásához
• Minden v csúcs esetében:
  • Legyen w az szomszédja v előfordulása v előtt, olyan közel v-hez amennyire lehetséges
    • (Folytassa a következő v csúccsal, ha nincs ilyen w )
  • Ha a v korábbi szomszédainak halmaza (kivéve magát w-t ) nem a w korábbi szomszédainak halmaza, a gráf nem húr
• Ha a húrok anélkül fejeződik be, hogy megmutatná, hogy a gráf nem húr, akkor az húr lesz..

Ez az alkalmazás volt a fő motiváció Rose, Tarjan & Lueker (1976)-nak,ami megalapozta a lexikográfiai szélességi keresési algoritmus kifejlesztését.

Gráf színezése

A G gráfról azt mondják, hogy tökéletesen megrendelhető, ha a csúcsai olyan sorrendben vannak, azzal a tulajdonsággal, hogy a G bármely indukált algráfja számára garantált, hogy egy kapzsi színező algoritmus, amely a csúcsokat az indukált sorrend sorrendben színezi, optimális színt eredményez.

A húr gráf esetében a tökéletes eliminációs sorrend tökéletes rendezés: bármely csúcshoz használt szín száma megegyezik az általa és korábbi szomszédai által létrehozott klikk méretével, tehát a felhasznált színek maximális száma megegyezik a a gráf legnagyobb klikkje, és egyetlen színezés sem használhat kevesebb színt. A húr-gráf indukált algráfja húr, és a tökéletes eliminációs sorrend indukált szekvenciája az al-grafikonon a tökéletes eliminációs sorrend, tehát a húr-gráfok tökéletesen megrendelhetők, és a lexikográfiai szélességi keresés felhasználható az optimális színezésre.

Ugyanez a tulajdonság igaz a nagyobb grafikonosztályra, a távolság-öröklődő grafikonokra : a távolság-öröklődő gráfok tökéletesen megrendelhetők, a tökéletes sorrendet a lexikográfiai sorrend fordítottja adja, tehát a lexikografikus szélességi keresés együttesen használható kapzsi színező algoritmusokkal, amelyek lineáris időben optimálisan színezik őket.

Egyéb alkalmazások

Bretscher et al. (2008) a lexikográfiai szélességi keresés kiterjesztését írják le, amely a bemeneti gráf komplement gráfja segítségével megszakít minden további köteléket. Amint azt megmutatják, ez felhasználható a krómozók lineáris időben történő felismerésére. Habib et al. (2000) leírják a lexikográfiai szélességi keresés további alkalmazását, beleértve az összehasonlíthatósági és az intervallum-gráfok felismerését.

LexBFS-rendezés

A gráfok csúcsainak felsorolását LexBFS-rendezésnek kell tekinteni, ha ez a LexBFS alkalmazásának lehetséges kimenete erre a gráfra.

Legyen $G=(V,E)$ legyen egy grafikon a $n$ csúcsa. Hívjuk meg $N(v)$ a szomszédok halmazát $v$. legyen $\sigma =(v_{1},\dots ,v_{n})$ a $V$ csúcsok felsorolása. A felsorolás $\sigma$ egy LexBFS rendezés ( $v_{1}$ kezdettel ) ha, minden $1\leq i<j<k\leq n$ val vel $v_{i}\in N(v_{j})\setminus N(v_{k})$, és létezik $m<i$ oly módon, hogy $v_{m}\in N(v_{j})\setminus V(v_{k})$.

Források

• Brandstädt, Andreas (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X, <https://archive.org/details/graphclassessurv0000bran>

• Brandstädt, Andreas (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X, <https://archive.org/details/graphclassessurv0000bran>
• Bretscher, Anna (2008), A simple linear time LexBFS cograph recognition algorithm, pp. 1277–1296, <http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps>
• Corneil, Derek G. (2004), Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Springer-Verlag, pp. 1–19
• Habib, Michel (2000), Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, pp. 59–84, <http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf>. Hozzáférés ideje: 2020-05-18 Archiválva 2011. július 26-i dátummal a Wayback Machine-ben
• Rose, D. J. (1976), Algorithmic aspects of vertex elimination on graphs, pp. 266–283

Fordítás

Ez a szócikk részben vagy egészben a Lexicographic breadth-first search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.